package william.tree;

import java.util.ArrayList;

/**
 * @author ZhangShenao
 * @date 2024/3/24
 * @description <a href="https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-100-liked">...</a>
 */
public class Leetcode230_二叉搜索树中第K小的元素 {
    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    /**
     * 采用递归算法
     * 对二叉树进行递归中序遍历,生成一个递增的有序数组
     * 直接返回数组的(k-1)下标位置的元素
     * <p>
     * 时间复杂度O(N) 对二叉树进行一次遍历
     * 空间复杂度 数组大小O(k)+递归栈深度O(logN)
     */
    public int kthSmallest(TreeNode root, int k) {
        //边界条件校验
        if (root == null || k < 1) {
            throw new IllegalArgumentException("invalid input!!");
        }

        //对二叉树进行递归中序遍历,生成一个递增的有序数组
        ArrayList<Integer> vals = new ArrayList<>();
        inorderTraversal(root, vals, k);

        //返回数组的(k-1)下标位置的元素
        return vals.get(k - 1);
    }

    /**
     * 递归实现
     * 对二叉树进行递归中序遍历,并将节点值保存在vals列表中
     */
    private void inorderTraversal(TreeNode root, ArrayList<Integer> vals, int k) {
        //递归终止条件
        if (root == null || vals.size() >= k) { //已经获取到了k个元素,可以提前终止
            return;
        }

        //递归遍历左子树
        inorderTraversal(root.left, vals, k);

        //保存根节点值
        vals.add(root.val);

        //递归遍历右子树
        inorderTraversal(root.right, vals, k);
    }
}
